package leetcode.dynamic;

/**
 * 定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：
 * <p>
 * "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
 * 给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "a"
 * 输出：1
 * 解释：字符串 s 的子字符串 "a" 在 base 中出现。
 * 示例 2：
 * <p>
 * 输入：s = "cac"
 * 输出：2
 * 解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。
 * 示例 3：
 * <p>
 * 输入：s = "zab"
 * 输出：6
 * 解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 105
 * s 由小写英文字母组成
 */
public class LeetCode467_FindSubstringInWraproundString {
    public int findSubstringInWraproundString(String s) {
        int[] dp = new int[26];
        char[] arr = s.toCharArray();

        for (int i = 0; i < arr.length; i++) {
            int len = 1;
            int idx = arr[i] - 'a';
            int j = i;

            // 会超时
            while (j - 1 >= 0) {
                if (arr[j - 1] == arr[j] - 1 || (arr[j - 1] == 'z' && arr[j] == 'a')) {
                    len++;
                    j--;
                } else {
                    break;
                }
            }
            dp[idx] = Math.max(dp[idx], len);
        }
        int ans = 0;
        for (int i : dp) {
            ans += i;
        }
        return ans;
    }

    public int findSubstringInWraproundString2(String s) {
        int[] dp = new int[26];
        char[] arr = s.toCharArray();
        dp[arr[0] - 'a'] = 1;

        int len = 1;
        for (int i = 1; i < arr.length; i++) {
            int idx = arr[i] - 'a';

            if (arr[i] == arr[i - 1] + 1 || (arr[i] == 'a' && arr[i - 1] == 'z')) {
                len++;
            } else {
                len = 1;
            }
            dp[idx] = Math.max(dp[idx], len);
        }

        int ans = 0;
        for (int i : dp) {
            ans += i;
        }
        return ans;
    }

    public static void main(String[] args) {
        LeetCode467_FindSubstringInWraproundString leetCode467_findSubstringInWraproundString = new LeetCode467_FindSubstringInWraproundString();
        int zaba = leetCode467_findSubstringInWraproundString.findSubstringInWraproundString("zaba");
        System.out.println("zaba = " + zaba);
    }
}
